package org.example;

/**
 * 回文链表
 */
public class Solution24 {

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        // 1. 找到链表的中间节点
        ListNode slow = head; // 慢指针
        ListNode fast = head; // 快指针

        // 快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针正好位于链表的中间节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. 反转链表的后半部分
        ListNode secondHalf = reverse(slow);
        ListNode firstHalf = head;

        //3. 比较前后两部分
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true;
    }

    /**
     * 辅助方法：反转链表
     * @param head
     * @return
     */
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }

}
